package leetcode; /**
 * description:
 * author:zt
 * date:2021-07-30
 */

/**
 * 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
 */
public class leetcode97 {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (s3.length()!= m+n) return false;
        // 动态规划，dp[i][j]表示s1前i字符能与s2前j字符组成s3前i+j个字符；
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        //第0行和第0列表示只有s1或只有s2时，s3能否由s1或s2组成 for循环不项目直接终止
        for (int i = 1; i < m + 1 && s1.charAt(i-1)==s3.charAt(i-1); i++) dp[i][0] = true;
        for (int i = 1; i < n + 1 && s2.charAt(i-1)==s3.charAt(i-1); i++) dp[0][i] = true;

        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                //dp[i-1][j]=true表示由s1的前i-1个字符和s2的前j个字符可以构成s3的前i+j-1个字符（注意charAt从0开始）
                //那么 要使dp[i][j]=true 需要s1的第i个字符等于s3的第i+j个字符 即s3.charAt(i+j-1)==s1.charAt(i-1)
                //dp[i][j-1]同理
                dp[i][j] = (dp[i-1][j] && s3.charAt(i+j-1)==s1.charAt(i-1)) ||
                        (dp[i][j-1] && s3.charAt(i+j-1)==s2.charAt(j-1));
            }
        }
        return dp[m][n];
    }
}
